package algorithm.dynamic_programming;

import java.util.HashMap;
import java.util.Map;

public class CoinWaySameValueSamePapper {

    public static class Info{
        public int[] coins;
        public int[] zhang;

        public Info(int[] coins, int[] zhang) {
            this.coins = coins;
            this.zhang = zhang;
        }
    }

    public static Info getInfo(int[] arr){
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i]))
                map.put(arr[i], map.get(arr[i]) + 1);
            else map.put(arr[i], 1);
        }
        int index = 0;
        int[] coins = new int[map.size()];
        int[] zhang = new int[map.size()];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            coins[index] = entry.getKey();
            zhang[index++] = entry.getValue();
        }
        return new Info(coins, zhang);
    }


    //将相同面值的纸币看作相同的纸币，只能取一张，求目标钱数的方案数。
    public static int ways1(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0)
            return 0;
        Info info = getInfo(arr);
        return process(info.coins, info.zhang, 0, aim);
    }
    public static int process(int[] coins, int[] zhang, int index, int rest){
        if(index == coins.length)
            return rest == 0? 1 : 0;
        int result = 0;
        for (int i = 0; i <= zhang[index] && rest - i * coins[index] >= 0; i++) {
            result += process(coins, zhang, index + 1, rest - i * coins[index]);
        }
        return result;
    }

    public static int ways2(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0)
            return 0;
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhang = info.zhang;
        int[][] dp = new int[coins.length + 1][aim + 1];
        dp[coins.length][0] = 1;
        for (int i = coins.length - 1; i >= 0; i--) {
            for (int j = 0; j < aim + 1; j++) {
                dp[i][j] = dp[i + 1][j];
                if(j - coins[i] >= 0){
                    int index = j - coins[i] - zhang[i] * coins[i];
                    dp[i][j] = index >= 0? dp[i][j] + dp[i][j -coins[i]] - dp[i + 1][index] : dp[i][j] + dp[i][j -coins[i]];
                }
            }
        }
        return dp[0][aim];
    }

    public static int[] randomArray(int maxLen, int maxValue) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxLen = 10;
        int maxValue = 20;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int aim = (int) (Math.random() * maxValue);
            int ans1 = ways1(arr, aim);
            int ans2 = ways2(arr, aim);
            if (ans1 != ans2) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(aim);
                System.out.println(ans1);
                System.out.println(ans2);
                break;
            }
        }
        System.out.println("测试结束");
    }
}
